﻿//int search(int* nums, int numsSize, int target)
//{
//	// 初始化 left 与 right 指针
//	int left = 0, right = numsSize - 1;
//	while (left <= right)
//	{
//		int mid = left + (right - left) / 2;
//		if (nums[mid] == target)
//			 return mid;
//		else if (nums[mid] > target) 
//			right = mid - 1;
//		else
//			 left = mid + 1;
//	}
//	return -1;
//}




//class Solution
//{
//public:
//	vector<int> searchRange(vector<int>& nums, int target)
//	{
//		// 处理边界情况
//		if (nums.size() == 0) 
//			return { -1, -1 };
//
//		int begin = 0;
//		// 1. ⼆分左端点
//		int left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] < target) 
//				left = mid + 1;
//			else
//				right = mid;
//		}
//		// 判断是否有结果
//		if (nums[left] != target) 
//			return { -1, -1 };
//		else
//			begin = left; // 标记⼀下左端点
//		// 2. ⼆分右端点
//		left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left + 1) / 2;
//			if (nums[mid] <= target) 
//				left = mid;
//			else 
//				right = mid - 1;
//		}
//		return { begin, right };
//	}
//};

//class Solution
//{
//public:
//	int searchInsert(vector<int>& nums, int target)
//	{
//		int left = 0, right = nums.size() - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] < target) 
//				left = mid + 1;
//			else 
//				right = mid;
//		}
//		if (nums[left] < target) 
//			return right + 1;
//		return right;
//	}
//};


//class Solution {
//public:
//	int mySqrt(int x) {
//		long long i = 0;
//		for (i = 0; i <= x; i++)
//		{
//			if (i * i == x)
//				return i;
//			if (i * i > x)
//				 return i - 1;
//		}
//		return -1;
//	}
//};



//class Solution
//{
//public:
//	int peakIndexInMountainArray(vector<int>& arr)
//	{
//		int left = 1, right = arr.size() - 2;
//		while (left < right)
//		{
//			int mid = left + (right - left + 1) / 2;
//			if (arr[mid] > arr[mid - 1]) 
//				left = mid;
//			else
//				right = mid - 1;
//		}
//		return left;
//	}
//};


//class Solution
//{
//public:
//	int peakIndexInMountainArray(vector<int>& arr)
//	{
//		int left = 1, right = arr.size() - 2;
//		while (left < right)
//		{
//			int mid = left + (right - left + 1) / 2;
//			if (arr[mid] > arr[mid - 1])
//				left = mid;
//			else 
//				right = mid - 1;
//		}
//		return left;
//	}
//};


//class Solution
//{
//public:
//	int findMin(vector<int>& nums)
//	{
//		int left = 0, right = nums.size() - 1;
//		int x = nums[right]; 
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] > x) 
//				left = mid + 1;
//			else 
//				right = mid;
//		}
//		return nums[left];
//	}
//};


class Solution
{
public:
	int missingNumber(vector<int>& nums)
	{
		int left = 0, right = nums.size() - 1;
		while (left < right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] == mid) 
				left = mid + 1;
			else
				right = mid;
		}
		return left == nums[left] ? left + 1 : left;
	}
};